#include <vector>
#include <iostream>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 思路: DFS(深度优先)找到从根节点到p和q的路径，比较两条路径找到最后一个相同节点即为最近公共祖先
class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        vector<TreeNode *> path;
        vector<TreeNode *> path_p;
        vector<TreeNode *> path_q;
        dfs(root, p, q, path, path_p, path_q); // 找到从根节点到p和q的路径
        TreeNode *res = NULL;
        for (int i = 0; i < min(path_p.size(), path_q.size()); ++i)
        {
            if (path_p[i] == path_q[i])
            {
                res = path_p[i];
            }
            else
            {
                break;
            }
        }
        return res;
    }
    // DFS找到从根节点到p和q的路径
    void dfs(TreeNode *node, TreeNode *p, TreeNode *q, vector<TreeNode *> &path,
             vector<TreeNode *> &path_p, vector<TreeNode *> &path_q)
    {
        if (!node || !path_p.empty() && !path_q.empty()) // 剪枝: 当前节点为空或两条路径都已找到
            return;
        path.push_back(node); // 将当前节点加入路径
        if (node == p)        // 找到p节点
            path_p = path;
        if (node == q) // 找到q节点
            path_q = path;
        if (path_p.empty() || path_q.empty()) // 其中一条路径未找到，继续DFS
        {
            dfs(node->left, p, q, path, path_p, path_q);
            dfs(node->right, p, q, path, path_p, path_q);
        }
        path.pop_back(); // 回溯: 移除当前节点
    }
};